In a computer network, or in a switching network, credit based flow control is used to control the amount of data transmitted by a source node so that there is always a buffer available in the destination node to hold the data. Frequently the data is divided into discrete packets. In some systems, such as the Asynchronous Transfer Mode (ATM) protocol for transferring data in a computer network, the data is placed into cells. ATM cells are 53 bytes in length, with 48 of the bytes carrying data and 5 of the bytes comprising a header. When a message larger than 48 bytes is transferred from a source node to a destination node, the source node first breaks down the larger message into 48 byte data cells, and the destination node later reassembles the 48 byte data cells into a received message identical to the transmitted message.
In some message transfer protocols, such as the ATM protocol, the intermediate nodes are switches. The switches route cells along virtual circuits (VCs). Each endstation which is a source node has a virtual circuit established to a destination endstation. The intermediate nodes, or switches, handle all of the virtual circuits which are routed through them. In a typical network established according to the ATM protocol, an intermediate node may have several thousands of virtual circuits routed through it.
Further, in some network protocols such as the ATM protocol, a cell which is lost at an intermediate node cannot be retransmitted by the source endstation because no mechanism is employed to track individual cells. Cells in the ATM protocol are simply transmitted in serial order. In the event that a cell is lost, the entire message is again broken down into cells and the sequence of cells again transmitted, according to the ATM protocol. Therefore, in a network established according to a protocol such as the ATM protocol, it is important to keep intermediate nodes from losing cells.
To prevent loss of cells, hop-by-hop credit based flow control is introduced to control the transmission rate of each source station. For purposes of flow control, the source station may be an end station, or alternatively, the source station may be an intermediate node transmitting cells to a downstream intermediate node.
In credit based flow control, a virtual circuit is first assigned a number of credits which can be outstanding at any time. A credit, when held by a source node gives that source node permission to transmit one cell. When the cell is received by the destination node, the destination node keeps the credit until a buffer in the destination node which has received the cell is cleared of the received cell. After the buffer is cleared, the destination node returns a credit to the source node, thereby giving the source node permission to send another cell on that virtual circuit.
The number of outstanding credits assigned to a virtual circuit is chosen to permit the virtual circuit to operate at full available bandwidth. Thus, the number of outstanding credits assigned to the virtual circuit must be enough to fill the virtual circuit pipe during a round trip time period, plus an additional number to account for processing delays at the destination node. For example, the number of credits assigned to a virtual circuit may be on the order of ten (10) credits per virtual circuit.
In hop-by-hop credit based flow control, each intermediate node and the next downstream destination node maintains credit based flow control in order to ensure that the next downstream destination node has a buffer available to receive the next cell.
A problem arises when an intermediate node has thousands of virtual circuits, for example, with tens of credits assigned to each virtual circuit. The destination node stores the number of credits to be returned in each virtual circuit. A data structure to store the number of credits to be returned in each virtual circuit contains the virtual circuit number which may be 12 bits up to 24 bits. The memory requirement to hold a data structure of this size may run to 50,000 to 100,000 thousand bytes, or more.
A further problem is that the list of virtual circuits must be accessible in one cell time. That is, as a cell is being received, the list of credits must be updated. Fast access requires that the list of credits be implemented in a VLSI chip, where the VLSI chip implements the logic used to implement the credit based flow control.
It is, however, very expensive to maintain thousands of kilobytes of storage in a chip which implements the logic of credit based flow control.
It remains desirable to have a convenient and inexpensive way to maintain a list of credits to be returned in thousands of virtual circuits, and to have fast access to the list.